這題其實理解了好一陣子，假如有錯誤的地方麻煩幫我指證了

206. Reverse Linked List

// Question:
Reverse a singly linked list.

// Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {

}

Think

極限值/特殊狀況

• Linked List 裡面沒有 node
• 只有一個 node (所以反轉後還是它自己)

// 處理極端值
// linked list 裡面沒東西
if(!head){
    return null
}
// 只有一個值所以反轉之後還是他自己
if(!head.next){
    return head;
}

哪種資料結構解

• Linked List (範例都給你 ListNode 了)

大概會怎麼解

主要就是反轉指標，本來是 prev 的變成 next。

• 首先會定義三個東西
  • cur: 初始值 = head，然後判斷完會往下一個 node 移動 cur = cur.next
  • temp: 暫存 cur
  • prev: 初始值 = null，這個用來反轉指標

 let prev = null,
    cur = head,
    temp;

temp = cur;   // 用 temp 來存目前的 node，不然會被後面的操作影響
cur = cur.next;   // 目前的 node 指標先往下

// 將 next 指向先前的值
temp.next = prev; 

// prev 變成先前的值
prev = temp;

然後一直重覆以上步驟，直到結束 (current.next == null 代表結束了)

完整程式碼

var reverseList = function(head) {
    // 極端值
    // linked list 裡面沒東西
    if(!head){
        return null
    }
    // 只有一個值所以反轉之後還是他自己
    if(!head.next){
        return head;
    }

    let prev = null,
    cur = head,
    temp;
    
    while(cur != null){
        temp = cur;   // 用 temp 來存目前的 node，不然會被後面的操作影響
        cur = cur.next;   // 目前的 node 指標先往下

        // 將 next 指向先前的值
        temp.next = prev; 

        // prev 變成先前的值
        prev = temp;
    }

    return prev;

};

自己思考 Linked List 時的確花了更多時間來理解，不過學東西本來就這樣嘛，一開始總是辛苦，後來會發現是值得的。有邦友說 Linked List 在 React 底層有用到，雖然我們不太可能去親手打造一個 library，但懂這個資料結構在做甚麼我覺得是蠻重要的，有機會看底層的實作流程吸取大師經驗也能比較上手一些。

如有錯誤或需要改進的地方，拜託跟我說。
我會以最快速度修改，感謝您

歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。